import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class Test0907 {
    //二叉树遍历
    public static void main(String[] args) {
        TreeNode treeNode = tool();
        List<Integer> resultRecursive = new ArrayList<>();
        List<Integer> resultIterative = new ArrayList<>();
        List<Integer> resultPostorder = new ArrayList<>();
        List<Integer> resultInorder = new ArrayList<>();
        BinaryTreeTraversal binaryTreeTraversal = new BinaryTreeTraversal();

        binaryTreeTraversal.preorderRecursive(treeNode, resultRecursive);
        System.out.println("先序遍历（递归）：" + resultRecursive);//68,23,15,47,91

        binaryTreeTraversal.preorderIterative(treeNode, resultIterative);
        System.out.println("先序遍历（迭代）：" + resultIterative);

        binaryTreeTraversal.postorderIterative(treeNode, resultPostorder);
        System.out.println("后序遍历（迭代）：" + resultPostorder);//15,47,23,91,68

        binaryTreeTraversal.inorderIterative(treeNode, resultInorder);
        System.out.println("中序遍历（迭代）：" + resultInorder);//15,23,47,68,91
    }

    //示例二叉树
    public static TreeNode tool() {
        TreeNode root = new TreeNode(68);//          68
        root.left = new TreeNode(23);//            /    \
        root.right = new TreeNode(91);//          23    91
        root.left.left = new TreeNode(15);//     /  \
        root.left.right = new TreeNode(47);//   15  47

        return root;
    }
}

//红黑树定义
class RBTreeNode {

    RBTreeNode left;
    RBTreeNode right;
    RBTreeNode parent;
    COLOR color;
    int val;

    public RBTreeNode(int val) {
        this.val = val;
        this.left = null;
        this.right = null;
        this.parent = null;
        this.color = COLOR.RED;
    }
}

class RedBlackTreeNode {
    private RBTreeNode root;
    private RBTreeNode NIL;

    public RedBlackTreeNode() {
        NIL = new RBTreeNode(0);
        NIL.color = COLOR.BLACK;
        root = NIL;
    }

    //左旋
    private void leftRotate(RBTreeNode x) {
        RBTreeNode y = x.right;
        x.right = y.left;

        if (y.left != NIL) {
            y.left.parent = x;
        }

        y.parent = x.parent;

        if (x.parent == NIL) {
            root = y;
        } else if (x == x.parent.left) {
            x.parent.left = y;
        } else {
            x.parent.right = y;
        }

        y.left = x;
        x.parent = y;
    }

    private void rightRotate(RBTreeNode x) {
        RBTreeNode y = x.left;
        x.left = y.right;

        if (y.right != NIL) {
            y.right.parent = x;
        }

        y.parent = x.parent;

        if (x.parent == NIL) {
            root = y;
        } else if (x == x.parent.left) {
            x.parent.left = y;
        } else {
            x.parent.right = y;
        }

        y.right = x;
        x.parent = y;
    }

    private void insertFix(RBTreeNode x) {
        while (x.parent.color == COLOR.RED) {
            if (x.parent == x.parent.parent.left) {
                RBTreeNode uncle = x.parent.parent.right;

                if (uncle.color == COLOR.RED) {
                    uncle.color = COLOR.BLACK;
                    x.parent.color = COLOR.BLACK;
                    x.parent.parent.color = COLOR.RED;
                    x = x.parent.parent;
                } else {
                    if (x == x.parent.right) {
                        x = x.parent;
                        leftRotate(x);
                    }
                    x.parent.color = COLOR.BLACK;
                    x.parent.parent.color = COLOR.RED;
                    rightRotate(x.parent.parent);
                }
            } else {
                RBTreeNode uncle = x.parent.parent.left;

                if (uncle.color == COLOR.RED) {
                    uncle.color = COLOR.BLACK;
                    x.parent.color = COLOR.BLACK;
                    x.parent.parent.color = COLOR.RED;
                    x = x.parent.parent;
                } else {
                    if (x == x.parent.left) {
                        x = x.parent;
                        rightRotate(x);
                    }
                    x.parent.color = COLOR.BLACK;
                    x.parent.parent.color = COLOR.RED;
                    leftRotate(x.parent.parent);
                }
            }
        }
        root.color = COLOR.BLACK;
    }

    public void insert(int val) {
        RBTreeNode z = new RBTreeNode(val);
        z.left = NIL;
        z.right = NIL;

        RBTreeNode x = NIL;
        RBTreeNode y = root;

        while (y != NIL) {
            x = y;
            if (z.val > y.val) {
                y = y.right;
            } else {
                y = y.left;
            }
        }

        z.parent = x;
        if (x == NIL) {
            root = z;
        } else if (x.val > z.val) {
            x.left = z;
        } else {
            x.right = z;
        }

        if (z.parent == NIL) {
            z.color = COLOR.BLACK;
            return;
        }
        if (z.parent.parent == NIL) {
            return;
        }

        insertFix(z);
    }
}

//二叉树定义
class TreeNode {
    TreeNode left = null;
    TreeNode right = null;
    int val;

    public TreeNode(int val) {
        this.val = val;
    }
}

//遍历二叉树
class BinaryTreeTraversal {
    //先序递归
    public void preorderRecursive(TreeNode root, List<Integer> result) {
        if (root == null) {
            return;
        }

        result.add(root.val);
        preorderRecursive(root.left, result);
        preorderRecursive(root.right, result);
    }

    //先序迭代
    public void preorderIterative(TreeNode root, List<Integer> result) {
        if (root == null) {
            return;
        }

        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);

        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            result.add(node.val);

            if (node.right != null) {
                stack.push(node.right);
            }
            if (node.left != null) {
                stack.push(node.left);
            }
        }
    }

    //中序迭代
    public void inorderIterative(TreeNode root, List<Integer> result) {
        if (root == null) {
            return;
        }

        Stack<TreeNode> stack = new Stack<>();
        TreeNode node = root;

        while (!stack.isEmpty() || node != null) {
            while (node != null) {
                stack.push(node);
                node = node.left;
            }

            node = stack.pop();
            result.add(node.val);

            node = node.right;
        }
    }

    //后序迭代
    public void postorderIterative(TreeNode root, List<Integer> result) {
        if (root == null) {
            return;
        }

        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        TreeNode yesterday = null;

        while (!stack.isEmpty()) {
            TreeNode node = stack.peek();

            //叶子节点或上次是子树
            if ((node.left == null && node.right == null)
                || ((yesterday != null) && (yesterday == node.left || yesterday == node.right))) {
                stack.pop();
                result.add(node.val);
                yesterday = node;
            } else {
                if (node.right != null) {
                    stack.push(node.right);
                }
                if (node.left != null) {
                    stack.push(node.left);
                }
            }
        }
    }
}

class Sort {
    //快速排序
    void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            int tool = partition(arr, low, high);

            quickSort(arr, low, tool - 1);
            quickSort(arr, tool + 1, high);
        }
    }

    int partition(int[] arr, int low, int high) {
        int pivot = arr[high];
        int i = low - 1;

        for (int j = low; j < high; j++) {
            if (arr[j] <= pivot) {
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }

        int temp = arr[i + 1];
        arr[i + 1] = arr[high];
        arr[high] = temp;

        return i + 1;
    }

    //归并排序
    void mergeSort(int[] arr, int left, int right) {
        if (left < right) {
            int mid = (left + right) / 2;

            mergeSort(arr, left, mid);
            mergeSort(arr, mid + 1, right);

            merge(arr, left, mid, right);
        }
    }

    void merge(int[] arr, int left, int mid, int right) {
        int n1 = mid - left + 1;
        int n2 = right - mid;

        int[] L = new int[n1];
        int[] R = new int[n2];

        System.arraycopy(arr, left, L, 0, n1);
        System.arraycopy(arr, mid + 1, R, 0, n2);

        int i = 0;
        int j = 0;
        int k = left;

        while (i < n1 && j < n2) {
            if (L[i] <= R[j]) {
                arr[k++] = L[i++];
            } else {
                arr[k++] = R[j++];
            }
        }

        while (i < n1) {
            arr[k++] = L[i++];
        }
        while (j < n2) {
            arr[k++] = R[j++];
        }
    }

    //堆排序
    void heapSort(int[] arr) {
        int n = arr.length;

        for (int i = n/2 - 1; i >= 0; i--) {
            heapify(arr, n, i);
        }//父比子大

        for (int i = n - 1; i >= 0; i--) {
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;
            heapify(arr, i, 0);//最小子（根）换此时最大值
        }
    }

    void heapify(int[] arr, int n, int i) {
        int largest = i;
        int left = 2*i + 1;
        int right = 2*i + 2;

        if (left < n && arr[left] > arr[largest]) {
            largest = left;
        }
        if (right < n && arr[right] > arr[largest]) {
            largest = right;
        }

        if (largest != i) {
            int temp = arr[largest];
            arr[largest] = arr[i];
            arr[i] = temp;
            heapify(arr, n, largest);
        }
    }
}